﻿#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<chrono>
#include<iomanip>
using namespace std;

// ==================== KMP算法实现 ====================
void getNext(string p, vector<int>& next, int& compareCount) {
    int m = p.length();
    next[0] = 0;
    int k = 0;

    for (int j = 1; j < m; j++) {
        while (k > 0 && p[j] != p[k]) {
            compareCount++;
            k = next[k - 1];
        }
        compareCount++;
        if (p[j] == p[k]) {
            k++;
        }
        next[j] = k;
    }
}

int KMP(string t, string p, vector<int>& next, int& compareCount) {
    int n = t.length();
    int m = p.length();
    int j = 0;

    for (int i = 0; i < n; i++) {
        while (j > 0 && t[i] != p[j]) {
            compareCount++;
            j = next[j - 1];
        }
        compareCount++;
        if (t[i] == p[j]) {
            j++;
        }
        if (j == m) {
            return i - m + 1;
        }
    }
    return -1;
}

// ==================== BM算法实现 ====================
void buildBadChar(string p, vector<int>& badChar) {
    int m = p.length();
    badChar.assign(256, -1);
    for (int i = 0; i < m; i++) {
        badChar[(int)p[i]] = i;
    }
}

void computeSuffixes(string p, vector<int>& suffix) {
    int m = p.length();
    suffix.assign(m, 0);
    suffix[m - 1] = m;

    for (int i = m - 2; i >= 0; i--) {
        int j = 0;
        while (j <= i && p[i - j] == p[m - 1 - j]) {
            j++;
        }
        suffix[i] = j;
    }
}

void buildGoodSuffix(string p, vector<int>& goodSuffix) {
    int m = p.length();
    goodSuffix.assign(m, m);
    vector<int> suffix(m);
    computeSuffixes(p, suffix);

    for (int i = m - 1; i >= 0; i--) {
        if (suffix[i] == i + 1) {
            for (int j = 0; j < m - 1 - i; j++) {
                if (goodSuffix[j] == m) {
                    goodSuffix[j] = m - 1 - i;
                }
            }
        }
    }

    for (int i = 0; i < m - 1; i++) {
        goodSuffix[m - 1 - suffix[i]] = m - 1 - i;
    }
}

int BM(string t, string p, int& compareCount) {
    int n = t.length();
    int m = p.length();

    vector<int> badChar;
    vector<int> goodSuffix;
    buildBadChar(p, badChar);
    buildGoodSuffix(p, goodSuffix);

    int shift = 0;

    while (shift <= n - m) {
        int j = m - 1;
        while (j >= 0) {
            compareCount++;
            if (p[j] != t[shift + j]) {
                break;
            }
            j--;
        }

        if (j < 0) {
            return shift;
        }
        else {
            int badCharShift = j - badChar[(int)t[shift + j]];
            int goodSuffixShift = goodSuffix[j];
            shift += max(max(1, badCharShift), goodSuffixShift);
        }
    }

    return -1;
}

// ==================== 工具函数 ====================

// 生成指定字符集的随机字符串
string generateRandomString(int length, char minChar, char maxChar) {
    string result;
    result.reserve(length);
    int range = maxChar - minChar + 1;

    for (int i = 0; i < length; i++) {
        result += (char)(minChar + rand() % range);
    }

    return result;
}

// 从主串中提取子串作为模式串（确保能找到匹配）
string extractPattern(const string& text, int position, int length) {
    if (position + length > text.length()) {
        position = text.length() - length;
    }
    return text.substr(position, length);
}

// 获取随机长度（在指定范围内）
int getRandomLength(int minLen, int maxLen) {
    return minLen + rand() % (maxLen - minLen + 1);
}

// ==================== 实验结构体 ====================
struct TestResult {
    string charsetName;      // 字符集名称
    string lengthType;       // 长度类型：短/中/长
    string position;         // 位置：前/中/后
    int patternLength;       // 实际模式串长度
    int kmpCompares;         // KMP比较次数
    int bmCompares;          // BM比较次数
    double kmpTime;          // KMP时间(微秒)
    double bmTime;           // BM时间(微秒)
    int kmpPos;              // KMP找到的位置
    int bmPos;               // BM找到的位置
};

// ==================== 实验执行函数 ====================
TestResult runTest(const string& text, const string& pattern,
    const string& charsetName, const string& lengthType,
    const string& position) {
    TestResult result;
    result.charsetName = charsetName;
    result.lengthType = lengthType;
    result.position = position;
    result.patternLength = pattern.length();

    // 测试KMP
    vector<int> next(pattern.length());
    result.kmpCompares = 0;
    getNext(pattern, next, result.kmpCompares);

    auto kmpStart = chrono::high_resolution_clock::now();
    result.kmpPos = KMP(text, pattern, next, result.kmpCompares);
    auto kmpEnd = chrono::high_resolution_clock::now();
    result.kmpTime = chrono::duration<double, micro>(kmpEnd - kmpStart).count();

    // 测试BM
    result.bmCompares = 0;
    auto bmStart = chrono::high_resolution_clock::now();
    result.bmPos = BM(text, pattern, result.bmCompares);
    auto bmEnd = chrono::high_resolution_clock::now();
    result.bmTime = chrono::duration<double, micro>(bmEnd - bmStart).count();

    return result;
}

// ==================== 输出结果函数 ====================
void printResults(const vector<TestResult>& results, const string& charsetName) {
    cout << "\n========================================\n";
    cout << "字符集: " << charsetName << "\n";
    cout << "========================================\n";

    for (const auto& r : results) {
        if (r.charsetName == charsetName) {
            cout << "模式串长度: " << r.lengthType
                << " : 位置: " << r.position
                << " : 实际长度: " << r.patternLength
                << " : KMP比较次数: " << r.kmpCompares
                << " : BM比较次数: " << r.bmCompares
                << " : KMP时间(μs): " << fixed << setprecision(2) << r.kmpTime
                << " : BM时间(μs): " << r.bmTime
                << " : 比较次数比值: " << setprecision(2) << (double)r.kmpCompares / r.bmCompares
                << " : 时间比值: ";

            if (r.bmTime > 0) {
                cout << setprecision(2) << r.kmpTime / r.bmTime;
            }
            else {
                cout << "inf";
            }
            cout << endl;
        }
    }
}

void printSummary(const vector<TestResult>& results) {
    int totalKmpCompares = 0;
    int totalBmCompares = 0;
    double totalKmpTime = 0;
    double totalBmTime = 0;

    for (const auto& r : results) {
        totalKmpCompares += r.kmpCompares;
        totalBmCompares += r.bmCompares;
        totalKmpTime += r.kmpTime;
        totalBmTime += r.bmTime;
    }

    cout << "\n========================================\n";
    cout << "总体统计\n";
    cout << "========================================\n";
    cout << "总测试用例数: " << results.size() << endl;
    cout << "KMP总比较次数: " << totalKmpCompares << endl;
    cout << "BM总比较次数: " << totalBmCompares << endl;
    cout << "比较次数比值 (KMP/BM): " << fixed << setprecision(2)
        << (double)totalKmpCompares / totalBmCompares << endl;
    cout << "KMP总时间: " << setprecision(2) << totalKmpTime << " μs" << endl;
    cout << "BM总时间: " << setprecision(2) << totalBmTime << " μs" << endl;
    if (totalBmTime > 0) {
        cout << "时间比值 (KMP/BM): " << setprecision(2)
            << totalKmpTime / totalBmTime << endl;
    }
    cout << "========================================\n";
}

// ==================== 主实验函数 ====================
int main() {
    // 设置随机种子
    srand(time(0));

    cout << " KMP与BM算法性能比较实验\n";


    // 实验参数
    const int TEXT_LENGTH = 10000;

    // 定义测试场景
    struct Charset {
        string name;
        char minChar;
        char maxChar;
    };

    vector<Charset> charsets = {
        {"二进制 [0,1]", '0', '1'},
        {"十进制 [0-9]", '0', '9'},
        {"ASCII可见字符 [32-126]", 32, 126}
    };

    // 定义长度范围
    struct LengthRange {
        string name;
        int minLen;
        int maxLen;
    };

    vector<LengthRange> lengths = {
        {"短 (5-10)", 5, 10},
        {"中 (50-100)", 50, 100},
        {"长 (500-1000)", 500, 1000}
    };

    // 定义位置
    vector<string> positions = { "前部", "中部", "后部" };

    // 存储所有测试结果
    vector<TestResult> allResults;

    // 执行测试
    for (const auto& charset : charsets) {
        cout << "\n 测试场景: " << charset.name << endl;

        // 生成主串
        string text = generateRandomString(TEXT_LENGTH, charset.minChar, charset.maxChar);

        for (const auto& lengthRange : lengths) {
            for (const auto& pos : positions) {
                // 确定模式串的位置
                int patternPos;
                if (pos == "前部") {
                    patternPos = rand() % (TEXT_LENGTH / 3);
                }
                else if (pos == "中部") {
                    patternPos = TEXT_LENGTH / 3 + rand() % (TEXT_LENGTH / 3);
                }
                else {  // 后部
                    patternPos = 2 * TEXT_LENGTH / 3 + rand() % (TEXT_LENGTH / 3);
                }

                // 生成模式串长度
                int patternLen = getRandomLength(lengthRange.minLen, lengthRange.maxLen);

                // 提取模式串
                string pattern = extractPattern(text, patternPos, patternLen);

                // 运行测试
                TestResult result = runTest(text, pattern, charset.name,
                    lengthRange.name, pos);
                allResults.push_back(result);

                // 实时输出进度
                cout << "  [" << lengthRange.name << " - " << pos << "] "
                    << "长度=" << result.patternLength
                    << ", KMP=" << result.kmpCompares
                    << ", BM=" << result.bmCompares << endl;
            }
        }
    }

    // 输出完整报告
    cout << "\n\n========================================\n";
    cout << "详细实验结果\n";
    cout << "========================================\n";

    for (const auto& charset : charsets) {
        printResults(allResults, charset.name);
    }

    printSummary(allResults);

    cout << "\n实验完成！\n";

    return 0;
}